# 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
# 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
# 最后发现3最快


class Solution:
    def findSubstring(self, s, words):
        len_s = len(s)
        len_words = len(words)
        if (len_s == 0) or (len_words == 0):
            return []
        len_one_word = len(words[0])
        res = []
        for word in words:
            i = 0
            while i <= (len_s - len_one_word * (len_words-1) - 1):
                if s[i:].startswith(word):
                    mid_words = words[:]
                    mid_words.remove(word)
                    if len(mid_words) == 0:
                        res.append(i)
                    elif self.find_son(s[i+len_one_word:], mid_words):
                        res.append(i)
                i += 1
        return list(set(res))

    def find_son(self, s, words):
        if len(words) == 1:
            return s.startswith(words[0])
        len_one_word = len(words[0])
        if s[:len_one_word] in words:
            mid_words = words[:]
            mid_words.remove(s[:len_one_word])
            if self.find_son(s[len_one_word:], mid_words):
                return True
        else:
            return False

    def findSubstring2(self, s, words):
        len_s, len_words = len(s), len(words)
        if (len_s == 0) or (len_words == 0):
            return []
        res = []
        word_dic = {}
        for one_word in words:
            if one_word in word_dic:
                word_dic[one_word] += 1
            else:
                word_dic[one_word] = 1
        title_dic, len_one_word = {}, len(words[0])
        for i in range(0, len_s - len_one_word+1):
            if s[i:i + len_one_word] in words:
                if s[i:i + len_one_word] in title_dic:
                    title_dic[s[i:i + len_one_word]].append(i)
                else:
                    title_dic[s[i:i + len_one_word]] = [i]
        for i in range(0, len(s) - len_words * len_one_word + 1):
            for word in word_dic:
                count = 0
                for num in title_dic[word]:
                    if i <= num < i + len_words * len_one_word and (num - i) % len_one_word == 0:
                        count += 1
                if count != word_dic[word]:
                    break
            else:
                res.append(i)
        return res

    def findSubstring3(self, s, words):
        len_s, len_words = len(s), len(words)
        if (len_s == 0) or (len_words == 0):
            return []
        res, word_dic = [], {}
        for one_word in words:
            if one_word in word_dic:
                word_dic[one_word] += 1
            else:
                word_dic[one_word] = 1
        len_one_word = len(words[0])
        for i in range(0, len(s) - len_words * len_one_word + 1):
            mid_dic = {}
            for num in range(0, len_words):
                mid_s = s[i + num * len_one_word:i + (num + 1) * len_one_word]
                if mid_s in word_dic:
                    if mid_s in mid_dic:
                        mid_dic[mid_s] += 1
                    else:
                        mid_dic[mid_s] = 1
                else:
                    break
            if mid_dic == word_dic:
                res.append(i)
        return res

    def findSubstring4(self, s, words):
        len_s, len_words = len(s), len(words)
        if (len_s == 0) or (len_words == 0):
            return []
        res, word_dic = [], {}
        for one_word in words:
            if one_word in word_dic:
                word_dic[one_word] += 1
            else:
                word_dic[one_word] = 1
        len_one_word, title_dic = len(words[0]), {}
        for i in range(0, len_s - len_one_word + 1):
            mid_s = s[i:i + len_one_word]
            if mid_s in words:
                title_dic[i] = mid_s
        print(title_dic)
        print(word_dic)
        for h in range(0, len(s) - len_words * len_one_word + 1):
            mid_dic = {}
            for num in range(0, len_words):
                if (h+num*len_one_word) in title_dic:
                    mid_word = title_dic[h+num*len_one_word]
                    if mid_word in mid_dic:
                        mid_dic[mid_word] += 1
                    else:
                        mid_dic[mid_word] = 1
                else:
                    break
            if mid_dic == word_dic:
                res.append(h)
        return res

a = Solution()
print(a.findSubstring4("barfoothefoobarman", ["foo", "bar"]))
print(a.findSubstring4("abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababa"
                      "babababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "babababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "ababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababababababababababababababababababababababababababababababababababababababab"
                      "abababababababababababababababababababababababababababababababababababababababababababababababa"
                      "babababababababababababababababababababababababababababababababababababababababababababababababa"
                      "bababababababababababa"
                       , ["ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba",
                          "ab","ba"]))

